As processing speeds of computer systems continue to increase, the ability to efficiently retrieve data from memory remains vital. The use of memory caches has been effective in compensating for speed mismatches between two levels of storage access, e.g., between a processor and main memory. Caches generally provide higher speed memory storage for recently/frequently used data in a computer system.
Improving the performance and utilization of caches remains an important aspect of computer system design. Typically, cache organizations and algorithms attempt to utilize the spatial and temporal localities of the storage access. Success in caches is usually measured by the hit ratio (i.e., the number of times that the needed data is found in the cache), as well as average access time (i.e., average time to locate and retrieve a piece of information and return it for processing), maximal throughput (i.e., maximal rate of data transfer), etc. At times, attempts to achieve better performance involve changes to the cache organization, which often improve hit ratios and access times at a slight expense of the maximal throughput due to cache replacing overhead.
For example, one typical method of improving performance by increasing the hit ratio involves expanding the size of the cache. Unfortunately, as the cache size is increased, an equivalent increase in the hit ratio percentage is not always achieved. For example, doubling a 4 GB (gigabytes) cache with a 75% hit ratio to 8 GB does not result in a doubling of the hit ratio. While a small percentage of improvement in the hit ratio occurs, the doubling in size results in considerable cost expenses.
Alternatively, with a fully compressed cache, an increase in storage capacity is achieved without increasing the cache size. When the compressed cache is used in a read-only environment, normally few problems in data integrity result. However, when used in an environment of changing data, significant problems result, mainly due to the need to have random access to the compressed data in the cache. Forming smaller, uniform-sized chunks within the compressed cache is sometimes used to allow more random access to portions of data. However, further complications in updating are created, since the compressed data may not elegantly fit within each chunk due to the size variations in the data. Further, compressing small chunks usually results in lower compression.
Accordingly, a need exists for a cache organization and algorithm that achieves results at least as effective as increasing a cache's size without the concomitant expense incurred by size increases.